Computer operating systems (OS) typically provide a mechanism for storing “objects” of data. Often, the OS dynamically allocates a sub-section of memory for utilization by an application into which the application places its objects. When the application finishes its utilization of a sub-section of memory, the OS may reclaim the memory. This process of reclamation is popularly known as garbage collection (GC).
Garbage collectors from the mark-sweep family suffer from memory fragmentation, which is the creation of holes of unused space between objects, the space being previously populated by objects that are no longer required by an application. To reduce fragmentation, a garbage collector may compact memory by moving utilized objects to reduce the unutilized space between them. This has the effect of combining small areas of unutilized memory into larger chunks of free space, making memory allocation more efficient, and reducing the memory footprint of the application. A goal of compaction algorithms is to create the largest chunks of free space possible within memory, thus enabling easy re-allocation by the OS.
Typically, a compaction algorithm run as part of a single process will aggregate objects to one “side” of the memory space, thus freeing up the rest of the memory space. While multi-process compaction algorithms take advantage of multiple processors and/or multiple threads to speed up memory compaction, each process typically works independently. These multiple, independent compactions typically create a number of sub-sections within the memory where the allocated objects are relocated to one side of each sub-section. This leaves memory organized locally into relatively large chunks, while still leaving memory relatively fragmented at the global level.